#include <iostream>
#include <vector>

using namespace std;
class Solution
{
public:
    vector<int> sortArrayByParityII(vector<int> &nums)
    {
        int n = nums.size();
        vector<int> ans(n);

        int i = 0;
        for (int x : nums)
        {
            if (x % 2 == 0)
            {
                ans[i] = x;
                i += 2;
            }
        }
        i = 1;
        for (int x : nums)
        {
            if (x % 2 == 1)
            {
                ans[i] = x;
                i += 2;
            }
        }
        return ans;
    }

    vector<int> sortArrayByParityII_2(vector<int> &nums)
    {
        int n = nums.size();
        int j = 1;
        for (int i = 0; i < n; i += 2)
        {
            if (nums[i] % 2 == 1)
            {
                while (nums[j] % 2 == 1)
                {
                    j += 2;
                }
                swap(nums[i], nums[j]);
            }
        }
        return nums;
    }
};
int main()
{
    Solution s;
    vector<int> nums = {4, 2, 5, 7};
    vector<int> ans = s.sortArrayByParityII(nums);
    for (auto &v : ans)
    {
        cout << v << " ";
    }
    cout << endl;
    return 0;
}